\documentclass{ctexart}

\usepackage{graphicx}
\usepackage{amsmath}

\title{作业三: \textbf{ValTree}区域打印的实现}


\author{胡宇梦 \\ 信息与计算科学　3210103435}


\begin{document}

\maketitle

\section{printRange函数代码的实现}

\begin{verbatim}
public：
    void printRange(Comparable& lower, Comparable& upper)
    {
        printRange(lower,upper,root);
    }
private：
    void printRange(Comparable& lower, Comparable& upper, AvlNode* t)
    {

        if (t != nullptr)
        {
            if (lower <= t->element)
                printRange(lower, upper, t->left);
            if (lower <= t->element && t->element <= upper)
                cout << t->element << endl;
            if (t->element <= upper)
                printRange(lower, upper, t->right);
        }
    }
\end{verbatim}

在已经构建了 AvlTree 这一个 class 之后，将 printRange 函数置于其 private 位置才能调用定义在private里面的root，
但是将其置于private位置，此函数不能被外部访问，所以此处利用函数重载，在public位置定义同名printRange函数，
调用public位置的printRange 函数进而调用private位置的printRange 函数。




\section{函数设计思路}

    printRange 函数使用递归的思想。从根部开始找寻，如果根部数据大于传入区域的最小值，则以根部左边的孩子为根部进行递
归，反之以右边的孩子为根部进行递归，如果有数据处于lower和upper之间，则将其输出。

\section{理论分析}
    此题可以称为一维范围搜索，叶子节点对应的是点，中间节点对应的是分支节点，搜索的结果就是两个叶子节点
    之间的所有叶子节点就是搜索的结果。

    如果找到大量节点，则执行无序遍历的时间为O（K）；如果我们
    到达了一些叶子（例如，如果找不到节点），则时间与树的深度成正比，对于AvlTree来讲，一棵AvlTree有
    N个节点，其高度可以保持在logN，所以查找的时间复杂度为O（logN）；
    
    
    因此，综上，一维范围搜索的时间复杂度可以给定为O（K+logN）。
\section{实验验证}
核心代码：
\begin{verbatim}
        for (double i = 0; i < 1000000; i++)
        {
            t.insert(i);
        } 
        if (k1 > k2)
        {
            cout << "It is a mistake!" << endl;
        }
        else
        {
            start = clock();
            t.printRange(k1, k2);
            stop = clock();
            duration = ((double)(stop - start)) / CLOCKS_PER_SEC;
            printf("dur = %lf", duration);
        }
\end{verbatim}
经过测试，总结结果，得出以下图像：
\begin{figure}[ht]
    \centering
    \includegraphics[width=7cm]{1.jpg}
    \caption{K为定值20时，时间随着N增大的变化曲线}
    \label{mode=1}
\end{figure}      

当K为定值20时，随着N增大，时间也逐渐增大，增大趋势基本符合logN的增长关系，所以验证
得出，AvlTree的查找时间复杂度为O（logN）。

\begin{figure}[ht]
    \centering
    \includegraphics[width=7cm]{2.jpg}
    \caption{N为定值100000时，时间随着K增加的变化曲线}
    \label{mode=1}
\end{figure}      
当N为定值100000时，随着K增大，时间也逐渐增大，增大趋势基本符合线性增长，符合理论要求。

综上，该算法的运行时间复杂度为O（K+logN）。
 


\end{document}
